EPR-dictionaries: A practical and fast data structure for constant time searches in unidirectional and bidirectional FM-indices

摘要

We introduce a new, practical method for conducting an exact search in a uni-and bidirectional FM index in $O(1)$ time per step while using $O(\log \sigma *n) + o(\log \sigma * \sigma * n)$ bits of space. This is done by replacing thebinary wavelet tree by a new data structure, the Enhanced Prefixsum Rankdictionary (EPR-dictionary). We implemented this method in the SeqAn C++library and experimentally validated our theoretical results. In addition wecompared our implementation with other freely available implementations ofbidirectional indices and show that we are between $\approx 2.6-4.8$ timesfaster. This will have a large impact for many bioinformatics applications thatrely on practical implementations of (2)FM indices e.g. for read mapping. Toour knowledge this is the first implementation of a constant time method for asearch step in 2FM indices.